package lee.meiriyiti.day1117;

public class TestDemo1117_2 {

    public static int reverse(int[] array, int n) {
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (array[i] > array[j])
                    count++;
            }
        }
        return count;
    }

    //归并思路
    public static int reverse2(int[] array, int n) {
        if (array == null || n == 0) return 0;
        else return mergesort(array, 0, n - 1);
    }

    public static int mergesort(int[] array, int left, int right) {
        if (left == right) return 0;//数组只有一个元素的情况
        int mid = (left + right) / 2;
        return mergesort(array, left, mid) + mergesort(array, mid + 1, right)
                + merge(array, left, mid, right);
    }

    public static int merge(int[] array, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];//建立一个数组用来保存排序后的数组
        int index = 0;//数组的下标
        int l = left;
        int r = mid + 1;//l，r分别用来表示两段数组的起始下标
        int reverseNum = 0;//记录逆序对个数
        while (l <= mid && r <= right) {
            if (array[l] <= array[r]) {
                tmp[index++] = array[l++];
            } else {
                reverseNum += (mid - l + 1);
                tmp[index++] = array[r++];
            }
        }
        while (l <= mid) {
            tmp[index++] = array[l++];
        }
        while (r <= right) {
            tmp[index++] = array[r++];
        }
        for (int k = 0; k < tmp.length; k++) {
            array[left++] = tmp[k];
        }
        return reverseNum;
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 0};
        System.out.println(reverse2(array, array.length));
    }
}
